package com.zsjt.dynamicprogramming;

import java.util.Scanner;

/**
 * @author ZhanBo
 * @date 2020/8/1
 */
public class Backpack01 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        /*输入背包的最大重量*/
        int maxWeight = scanner.nextInt();
        /*输入物品的数目*/
        int numbers = scanner.nextInt();
        /*物品重量*/
        int [] weight = new int[numbers];
        /*物品价值*/
        int [] value = new int[numbers];

    }

    /**
     * 二维解法
     * 设f[i][j]表示前i件物品 总重量不超过j的最大价值 可得出状态转移方程 ：
     *  f[i][j]=max{f[i-1][j-w[i]]+v[i]，f[i-1][j]}
     *  w[i]：重量数组，v[i]:价值数组
     * @param maxWeight 输入背包的最大重量
     * @param weight 物品重量
     * @param value 物品价值
     * @return
     */
    public static int method1(int maxWeight, int[] weight, int[] value) {
        /*第一个值，不算*/
        int n = weight.length - 1;
        int[][] f = new int[n + 1][maxWeight + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = maxWeight; j >= weight[i]; j--) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
            }
        }
        /*最优解*/
        return f[n][maxWeight];
    }

    /**
     * 0,1背包：一维法
     * 用一维数组代替二维数组就解决了二维数组的问题
     * 设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程 ：
     * f[j]=max{f[j]，f[j−w[i]]+v[i]}
     * @param maxWeight
     * @param weight
     * @param value
     * @return
     */
    public static int method2(int maxWeight, int[] weight, int[] value) {
        /* 第一个值，不算*/
        int n = weight.length - 1;
        int[] f = new int[maxWeight + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = maxWeight; j >= weight[i]; j--) {
                f[j] = Math.max(f[j], f[j - weight[i]] + value[i]);
            }
        }
        /*最优解*/
        return f[maxWeight];
    }
}
